public class QuickSort {


    public static void qsort(int[] nums, int start, int end){

        if(start >= end){
            return;
        }

        int index = partition(nums, start, end);
        qsort(nums, start, index - 1);
        qsort(nums, index + 1, end);
    }

    /**
     * 左边奇数，右边偶数
     * 找出奇数最大的下表，然后，走快排 partition，直接快排的思想，左右交互，最后返回中间的就可以了。
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public static int jiou(int[] nums, int start, int end){
        int i=start;
        int j=end;
        int pivot = nums[start];

        while (i < j){
            while ( i < j && nums[j] % 2 == 0){
                j--;
            }
            if( i < j ){
                nums[i++] = nums[j];
            }
            while ( i < j && nums[i] % 2 == 1){
                i++;
            }
            if( i < j ){
                nums[j--] = nums[i];
            }
            nums[i] = pivot;
        }

        return i;
    }

    public static void jiouSort(int[] nums, int start, int end){

        int pivot = jiou(nums, start, end);
        if(nums[pivot] % 2 == 1 && pivot < end){
            pivot++;
        }

        qsort(nums, start, pivot - 1);
        qsort(nums, pivot, end);
    }


    public static int partition(int[] nums, int start, int end){
        int index = nums[start];
        int i = start;
        int j = end;

        while(i < j){
            while (i < j && nums[j] >= index){
                j--;
            }
            //这个if很重要
            if(i < j){//碰到第一个右边的数小的，和左边的交换
                nums[i] = nums[j];i++;
            }
            while (i < j && nums[i] < index){
                i++;
            }
            if(i < j){
                nums[j--] = nums[i];
            }
            nums[i] = index;
        }
        return i;
    }

//    public static int partition(int[] nums, int from, int end){
//        int temp = nums[from];
//        while( from < end){
//            while(nums[end] > temp){
//                end--;
//
//            }
//        }
//    }

    public static void main(String[] args){
        int[] n = new int[]{1,9,3,2,54,213,4,56,7};

        QuickSort.jiouSort(n, 0, n.length - 1);

        QuickSort.qsort(n, 0, n.length - 1);

        System.out.println(n);
    }
}
